package com.yize.leetcode;

import com.sun.xml.internal.ws.encoding.MtomCodec;
import org.junit.Test;

import java.util.*;

/**
 * 347. 前 K 个高频元素
 * 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
 *
 * 示例 1:
 *
 * 输入: nums = [1,1,1,2,2,3], k = 2
 * 输出: [1,2]
 * 示例 2:
 *
 * 输入: nums = [1], k = 1
 * 输出: [1]
 * 说明：
 *
 * 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
 * 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
 */
public class L347 {
    @Test
    public void test(){
        int[] nums={1,1,1,1,1,2};
        System.out.println(topKFrequent(nums,2));
        Math.max(1,2);
    }
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> list=new LinkedList<>();
        HashMap<Integer,Integer> map=new HashMap<>();
        for (int n:nums){
            if(!map.containsKey(n)){
                map.put(n,1);
            }else {
                map.put(n,map.get(n)+1);
            }
        }
        PriorityQueue<Integer> heap=new PriorityQueue<>((o1,o2)->map.get(o1)-map.get(o2));
        for (Integer n:map.keySet()){
            heap.offer(n);
            if(heap.size()>k){
                heap.poll();
            }
        }
        while (heap.size()>0){
            list.add(0,heap.poll());
        }
        return list;
    }

}
